Find the greatest common divisor (GCD) of two integers¶
Find the greatest common divisor (GCD) of two integers.
def gcd(a, b):
low = min(a, b)
high = max(a, b)
if low == 0:
return high
elif low == 1:
return 1
else:
return gcd(low, high % low)
# test
N, M = 12, 14
print(gcd(N, M)) # 2
def gcd_01(a, b):
return a if b == 0 else gcd_01(b, a % b)
# test
N, M = 1680, 640
print(gcd_01(N, M)) # 80
def gcd_02(a, b):
if a == b:
return a
elif a > b:
return gcd_02(a - b, b)
elif a < b:
return gcd_02(a, b - a)
# test
N, M = 1680, 640
print(gcd_02(N, M)) # 80